백준 9328번

열쇠

Posted by ChoiCube84 on January 07, 2024 · 52 mins read
프로그래밍 문제풀이

백준 9328번

오늘 풀어본 문제는 백준의 9328번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 $h$ 와 $w$ $(2 \le h, w \le 100)$ 가 주어진다. 다음 $h$ 개 줄에는 빌딩을 나타내는 $w$ 개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

  • ’$.$’는 빈 공간을 나타낸다.
  • ’$*$’는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
  • ’$$$’는 상근이가 훔쳐야하는 문서이다.
  • 알파벳 대문자는 문을 나타낸다.
  • 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 “$0$”이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 $0$ 개, $1$ 개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 $0$ 개, $1$ 개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

풀이과정

1번째 시도

문제를 보고 바로 알 수 있었다. 고통스러운 구현문제였다. BFS 를 이용하여 여러 번 탐색을 돌리는 방식으로 풀이를 시도하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

enum state {
    EMPTY = 0,
    // DOOR = 1 ~ 26
    WALL = 100,
    // KEY = 101 ~ 126
    DOC = 200
};

void simulate(void);

class Grid {
private:
    int height;
    int width;
    vector<vector<int>> grid;
    vector<pair<int, int>> entries;
    vector<bool> keys;
    int docCount;
public:
    Grid();
    bool checkBorder(pair<int, int> pos) const;

    bool update(pair<int, int> &lastPos);
    bool isInRange(pair<int, int> pos) const;

    int getDocCount() const;

};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;

    for (int i=0; i<T; i++) {
        simulate();
    }

    return 0;
}

void simulate(void) {
    Grid grid;
    pair<int, int> lastPos = make_pair(-1, -1);

    while (grid.update(lastPos)) {
        // grid.printGrid();
    }
    cout << grid.getDocCount() << "\n";
}

Grid::Grid() {
    docCount = 0;
    cin >> height >> width;

    grid.resize(height);
    keys.resize(26);

    for (int i=0; i < height; i++) {
        string row;
        cin >> row;

        grid[i].resize(width);
        for (int j=0; j < width; j++) {
            char c = row[j];

            if (checkBorder(make_pair(i, j))) {
                entries.emplace_back(i, j);
            }

            switch(c) {
                case '.':
                    grid[i][j] = EMPTY;
                    break;
                case '*':
                    grid[i][j] = WALL;
                    break;
                case '$':
                    grid[i][j] = DOC;
                    break;
                default:
                    if (c > 'Z') {
                        if (checkBorder(make_pair(i, j))) {
                            grid[i][j] = EMPTY;
                            keys[c - 'a'] = true;
                        }
                        else {
                            grid[i][j] = 100 + (c - 'a' + 1);
                        }
                    }
                    else {
                        grid[i][j] = c - 'A' + 1;
                    }
                    break;
            }
        }
    }

    string initialKeys;
    cin >> initialKeys;

    if (initialKeys != "0") {
        for (auto& key : initialKeys) {
            keys[key - 'a'] = true;
        }
    }
}

bool Grid::checkBorder(pair<int, int> pos) const {
    return !((pos.first % (height - 1)) * (pos.second % (width - 1)));
}

bool Grid::update(pair<int, int> &lastPos) {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    vector<vector<bool>> visited(height, vector<bool>(width, false));
    queue<pair<int, int>> q;

    if (isInRange(lastPos)) {
        q.push(lastPos);
    }

    for (auto entry : entries) {
        int currInfo = grid[entry.first][entry.second];

        switch (currInfo) {
            case EMPTY:
                q.push(entry);
                break;
            case WALL:
                break;
            case DOC:
                docCount++;
                grid[entry.first][entry.second] = EMPTY;
                return true;
            default:
                if (keys[currInfo - 1]) {
                    grid[entry.first][entry.second] = EMPTY;
                    return true;
                }
        }
    }

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();

        visited[curr.first][curr.second] = true;

        for (int i=0; i<4; i++) {
            auto next = make_pair(curr.first + dx[i], curr.second + dy[i]);
            if (isInRange(next) && !visited[next.first][next.second]) {
                int nextInfo = grid[next.first][next.second];
                switch (nextInfo) {
                    case EMPTY:
                        q.push(next);
                        break;
                    case WALL:
                        continue;
                    case DOC:
                        docCount++;
                        grid[next.first][next.second] = EMPTY;
                        lastPos = next;
                        return true;
                    default:
                        if (nextInfo > 100) {
                            keys[nextInfo - 101] = true;
                            grid[next.first][next.second] = EMPTY;
                            lastPos = next;
                            return true;
                        }
                        else {
                            if (keys[nextInfo - 1]) {
                                grid[next.first][next.second] = EMPTY;
                                lastPos = next;
                                return true;
                            }
                        }
                        break;
                }
            }
        }
    }

    return false;
}

bool Grid::isInRange(pair<int, int> pos) const {
    if (pos.first < 0 || pos.first > height - 1) {
        return false;
    }
    else if (pos.second < 0 || pos.second > width - 1) {
        return false;
    }
    else {
        return true;
    }
}

int Grid::getDocCount() const {
    return docCount;
}

실행 결과 ‘시간 초과’ 가 떴다.

2번째 시도

시간 초과를 해결하기 위해 처움 떠올린 것은, 입구를 설정할 때 빈 공간만 큐에 저장되도록 하도록 조건문을 변경하는 것이었다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

enum state {
    EMPTY = 0,
    // DOOR = 1 ~ 26
    WALL = 100,
    // KEY = 101 ~ 126
    DOC = 200
};

void simulate(void);

class Grid {
private:
    int height;
    int width;
    vector<vector<int>> grid;
    vector<pair<int, int>> entries;
    vector<bool> keys;
    int docCount;
public:
    Grid();
    bool checkBorder(pair<int, int> pos) const;

    bool update(pair<int, int> &lastPos);
    bool isInRange(pair<int, int> pos) const;

    int getDocCount() const;

};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;

    for (int i=0; i<T; i++) {
        simulate();
    }

    return 0;
}

void simulate(void) {
    Grid grid;
    pair<int, int> lastPos = make_pair(-1, -1);

    while (grid.update(lastPos)) {
        // grid.printGrid();
    }
    cout << grid.getDocCount() << "\n";
}

Grid::Grid() {
    docCount = 0;
    cin >> height >> width;

    grid.resize(height);
    keys.resize(26);

    for (int i=0; i < height; i++) {
        string row;
        cin >> row;

        grid[i].resize(width);
        for (int j=0; j < width; j++) {
            char c = row[j];

            if (checkBorder(make_pair(i, j)) && grid[i][j] == EMPTY) {
                entries.emplace_back(i, j);
            }

            switch(c) {
                case '.':
                    grid[i][j] = EMPTY;
                    break;
                case '*':
                    grid[i][j] = WALL;
                    break;
                case '$':
                    grid[i][j] = DOC;
                    break;
                default:
                    if (c > 'Z') {
                        if (checkBorder(make_pair(i, j))) {
                            grid[i][j] = EMPTY;
                            keys[c - 'a'] = true;
                        }
                        else {
                            grid[i][j] = 100 + (c - 'a' + 1);
                        }
                    }
                    else {
                        grid[i][j] = c - 'A' + 1;
                    }
                    break;
            }
        }
    }

    string initialKeys;
    cin >> initialKeys;

    if (initialKeys != "0") {
        for (auto& key : initialKeys) {
            keys[key - 'a'] = true;
        }
    }
}

bool Grid::checkBorder(pair<int, int> pos) const {
    return !((pos.first % (height - 1)) * (pos.second % (width - 1)));
}

bool Grid::update(pair<int, int> &lastPos) {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    vector<vector<bool>> visited(height, vector<bool>(width, false));
    queue<pair<int, int>> q;

    if (isInRange(lastPos)) {
        q.push(lastPos);
    }

    for (auto entry : entries) {
        int currInfo = grid[entry.first][entry.second];

        switch (currInfo) {
            case EMPTY:
                q.push(entry);
                break;
            case WALL:
                break;
            case DOC:
                docCount++;
                grid[entry.first][entry.second] = EMPTY;
                return true;
            default:
                if (keys[currInfo - 1]) {
                    grid[entry.first][entry.second] = EMPTY;
                    return true;
                }
        }
    }

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();

        visited[curr.first][curr.second] = true;

        for (int i=0; i<4; i++) {
            auto next = make_pair(curr.first + dx[i], curr.second + dy[i]);
            if (isInRange(next) && !visited[next.first][next.second]) {
                int nextInfo = grid[next.first][next.second];
                switch (nextInfo) {
                    case EMPTY:
                        q.push(next);
                        break;
                    case WALL:
                        continue;
                    case DOC:
                        docCount++;
                        grid[next.first][next.second] = EMPTY;
                        lastPos = next;
                        return true;
                    default:
                        if (nextInfo > 100) {
                            keys[nextInfo - 101] = true;
                            grid[next.first][next.second] = EMPTY;
                            lastPos = next;
                            return true;
                        }
                        else {
                            if (keys[nextInfo - 1]) {
                                grid[next.first][next.second] = EMPTY;
                                lastPos = next;
                                return true;
                            }
                        }
                        break;
                }
            }
        }
    }

    return false;
}

bool Grid::isInRange(pair<int, int> pos) const {
    if (pos.first < 0 || pos.first > height - 1) {
        return false;
    }
    else if (pos.second < 0 || pos.second > width - 1) {
        return false;
    }
    else {
        return true;
    }
}

int Grid::getDocCount() const {
    return docCount;
}

실행 결과 ‘시간 초과’ 가 떴다.

3번째 시도

다시 한 번 시간 초과를 해결하기 위해 이용한 방법은 keys 대신 doors 사용하여 문의 정보를 저장한 뒤, openDoors 함수를 이용하여 열쇠 획득 시 모든 문이 동시에 열리도록 하였다. 문제 조건에서 몇 번이고 열쇠를 쓸 수 있다고 했기 때문에 가능한 일이었다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

enum state {
    EMPTY = 0,
    // DOOR = 1 ~ 26
    WALL = 100,
    // KEY = 101 ~ 126
    DOC = 200
};

void simulate(void);

class Grid {
private:
    int height;
    int width;
    vector<vector<int>> grid;
    vector<pair<int, int>> entries;
    vector<pair<bool, vector<pair<int, int>>>> doors;
    int docCount;
public:
    Grid();
    void openDoors(int doorNum);
    bool checkBorder(pair<int, int> pos) const;

    bool update(pair<int, int> &lastPos);
    bool isInRange(pair<int, int> pos) const;

    int getDocCount() const;

    void printGrid();
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;

    for (int i=0; i<T; i++) {
        simulate();
    }

    return 0;
}

void simulate(void) {
    Grid grid;
    pair<int, int> lastPos = make_pair(-1, -1);

    while (grid.update(lastPos)) {
        // grid.printGrid();
    }
    cout << grid.getDocCount() << "\n";
}

Grid::Grid() {
    docCount = 0;
    cin >> height >> width;

    grid.resize(height);
    doors.resize(26);

    for (int i=0; i < height; i++) {
        string row;
        cin >> row;

        grid[i].resize(width);
        for (int j=0; j < width; j++) {
            char c = row[j];

            if (checkBorder(make_pair(i, j)) && grid[i][j] == EMPTY) {
                entries.emplace_back(i, j);
            }

            switch(c) {
                case '.':
                    grid[i][j] = EMPTY;
                    break;
                case '*':
                    grid[i][j] = WALL;
                    break;
                case '$':
                    grid[i][j] = DOC;
                    break;
                default:
                    if (c > 'Z') {
                        if (checkBorder(make_pair(i, j))) {
                            grid[i][j] = EMPTY;
                            doors[c - 'a'].first = true;
                        }
                        else {
                            grid[i][j] = 100 + (c - 'a' + 1);
                        }
                    }
                    else {
                        if (doors[c - 'A'].first) {
                            grid[i][j] = EMPTY;
                        }
                        else {
                            grid[i][j] = c - 'A' + 1;
                            doors[c - 'A'].second.emplace_back(i, j);
                        }
                    }
                    break;
            }
        }
    }

    string initialKeys;
    cin >> initialKeys;

    if (initialKeys != "0") {
        for (auto& key : initialKeys) {
            openDoors(key - 'a');
        }
    }
}

void Grid::openDoors(int doorNum) {
    doors[doorNum].first = true;
    for (auto& door : doors[doorNum].second) {
        grid[door.first][door.second] = EMPTY;
    }
}

bool Grid::checkBorder(pair<int, int> pos) const {
    return !((pos.first % (height - 1)) * (pos.second % (width - 1)));
}

bool Grid::update(pair<int, int> &lastPos) {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    vector<vector<bool>> visited(height, vector<bool>(width, false));
    queue<pair<int, int>> q;

    if (isInRange(lastPos)) {
        q.push(lastPos);
    }

    for (auto entry : entries) {
        int currInfo = grid[entry.first][entry.second];

        switch (currInfo) {
            case EMPTY:
                q.push(entry);
                break;
            case WALL:
                break;
            case DOC:
                docCount++;
                grid[entry.first][entry.second] = EMPTY;
                return true;
            default:
                break;
        }
    }

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();

        visited[curr.first][curr.second] = true;

        for (int i=0; i<4; i++) {
            auto next = make_pair(curr.first + dx[i], curr.second + dy[i]);
            if (isInRange(next) && !visited[next.first][next.second]) {
                int nextInfo = grid[next.first][next.second];
                switch (nextInfo) {
                    case EMPTY:
                        q.push(next);
                        break;
                    case WALL:
                        continue;
                    case DOC:
                        docCount++;
                        grid[next.first][next.second] = EMPTY;
                        lastPos = next;
                        return true;
                    default:
                        if (nextInfo > 100) {
                            openDoors(nextInfo - 101);
                            grid[next.first][next.second] = EMPTY;
                            lastPos = next;
                            return true;
                        }
                        break;
                }
            }
        }
    }

    return false;
}

bool Grid::isInRange(pair<int, int> pos) const {
    if (pos.first < 0 || pos.first > height - 1) {
        return false;
    }
    else if (pos.second < 0 || pos.second > width - 1) {
        return false;
    }
    else {
        return true;
    }
}

int Grid::getDocCount() const {
    return docCount;
}

void Grid::printGrid() {
    for (int i=0; i<height; i++) {
        for (int j=0; j<width; j++) {
            int currInfo = grid[i][j];

            switch (currInfo) {
                case EMPTY:
                    cout << ".";
                    break;
                case WALL:
                    cout << "*";
                    break;
                case DOC:
                    cout << "$";
                    break;
                default:
                    if (currInfo > 100) {
                        cout << static_cast<char>(currInfo - 101 + 'a');
                    }
                    else {
                        cout << static_cast<char>(currInfo - 1 + 'A');
                    }
                    break;
            }
        }
        cout << "\n";
    }
}

실행 결과 ‘시간 초과’ 가 떴다.

4번째 시도

이쯤되니 속이 너무 답답했다. 최후의 해결 방법으로 사용한 것은 visited 큐 밖으로 꺼내어 업데이트를 해주어 동일한 위치가 여러 번 들어가는 것을 막도록 하였고, maxDocCount 추가하여 모든 문서를 모으는데 성공했다면, 즉 더 모을 문서가 없다면 탐색을 중단하고 답을 출력하도록 하였다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

enum state {
    EMPTY = 0,
    // DOOR = 1 ~ 26
    WALL = 100,
    // KEY = 101 ~ 126
    DOC = 200
};

void simulate(void);

class Grid {
private:
    int height;
    int width;
    vector<vector<int>> grid;
    vector<pair<int, int>> entries;
    vector<pair<bool, vector<pair<int, int>>>> doors;
    int docCount;
    int maxDocCount;
public:
    Grid();
    void openDoors(int doorNum);
    bool checkBorder(pair<int, int> pos) const;

    bool update(pair<int, int> &lastPos);
    bool isInRange(pair<int, int> pos) const;

    int getDocCount() const;

    void printGrid();
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;

    for (int i=0; i<T; i++) {
        simulate();
    }

    return 0;
}

void simulate(void) {
    Grid grid;
    pair<int, int> lastPos = make_pair(-1, -1);

    while (grid.update(lastPos)) {
        // grid.printGrid();
    }
    cout << grid.getDocCount() << "\n";
}

Grid::Grid() {
    docCount = 0;
    maxDocCount = 0;
    
    cin >> height >> width;

    grid.resize(height);
    doors.resize(26);

    for (int i=0; i < height; i++) {
        string row;
        cin >> row;

        grid[i].resize(width);
        for (int j=0; j < width; j++) {
            char c = row[j];

            if (checkBorder(make_pair(i, j)) && grid[i][j] == EMPTY) {
                entries.emplace_back(i, j);
            }

            switch(c) {
                case '.':
                    grid[i][j] = EMPTY;
                    break;
                case '*':
                    grid[i][j] = WALL;
                    break;
                case '$':
                    grid[i][j] = DOC;
                    maxDocCount++;
                    break;
                default:
                    if (c > 'Z') {
                        if (checkBorder(make_pair(i, j))) {
                            grid[i][j] = EMPTY;
                            doors[c - 'a'].first = true;
                        }
                        else {
                            grid[i][j] = 100 + (c - 'a' + 1);
                        }
                    }
                    else {
                        if (doors[c - 'A'].first) {
                            grid[i][j] = EMPTY;
                        }
                        else {
                            grid[i][j] = c - 'A' + 1;
                            doors[c - 'A'].second.emplace_back(i, j);
                        }
                    }
                    break;
            }
        }
    }

    string initialKeys;
    cin >> initialKeys;

    if (initialKeys != "0") {
        for (auto& key : initialKeys) {
            openDoors(key - 'a');
        }
    }
}

void Grid::openDoors(int doorNum) {
    doors[doorNum].first = true;
    for (auto& door : doors[doorNum].second) {
        grid[door.first][door.second] = EMPTY;
    }
}

bool Grid::checkBorder(pair<int, int> pos) const {
    return !((pos.first % (height - 1)) * (pos.second % (width - 1)));
}

bool Grid::update(pair<int, int> &lastPos) {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    vector<vector<bool>> visited(height, vector<bool>(width, false));
    queue<pair<int, int>> q;

    if (isInRange(lastPos)) {
        q.push(lastPos);
        visited[lastPos.first][lastPos.second] = true;
    }

    for (auto entry : entries) {
        int currInfo = grid[entry.first][entry.second];

        switch (currInfo) {
            case EMPTY:
                q.push(entry);
                visited[entry.first][entry.second] = true;
                break;
            case WALL:
                break;
            case DOC:
                docCount++;
                grid[entry.first][entry.second] = EMPTY;
                if (docCount < maxDocCount) {
                    return true;
                }
                else {
                    return false;
                }
            default:
                break;
        }
    }

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();

        for (int i=0; i<4; i++) {
            auto next = make_pair(curr.first + dx[i], curr.second + dy[i]);
            if (isInRange(next) && !visited[next.first][next.second]) {
                int nextInfo = grid[next.first][next.second];
                switch (nextInfo) {
                    case EMPTY:
                        q.push(next);
                        visited[next.first][next.second] = true;
                        break;
                    case WALL:
                        continue;
                    case DOC:
                        docCount++;
                        grid[next.first][next.second] = EMPTY;
                        lastPos = next;
                        return true;
                    default:
                        if (nextInfo > 100) {
                            openDoors(nextInfo - 101);
                            grid[next.first][next.second] = EMPTY;
                            lastPos = next;
                            return true;
                        }
                        break;
                }
            }
        }
    }

    return false;
}

bool Grid::isInRange(pair<int, int> pos) const {
    if (pos.first < 0 || pos.first > height - 1) {
        return false;
    }
    else if (pos.second < 0 || pos.second > width - 1) {
        return false;
    }
    else {
        return true;
    }
}

int Grid::getDocCount() const {
    return docCount;
}

void Grid::printGrid() {
    for (int i=0; i<height; i++) {
        for (int j=0; j<width; j++) {
            int currInfo = grid[i][j];

            switch (currInfo) {
                case EMPTY:
                    cout << ".";
                    break;
                case WALL:
                    cout << "*";
                    break;
                case DOC:
                    cout << "$";
                    break;
                default:
                    if (currInfo > 100) {
                        cout << static_cast<char>(currInfo - 101 + 'a');
                    }
                    else {
                        cout << static_cast<char>(currInfo - 1 + 'A');
                    }
                    break;
            }
        }
        cout << "\n";
    }
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

정말 힘든 문제였다. CLASS 5 문제들은 하나하나가 머리가 아프고 사람 고생시키는 재주가 있는 것 같다… 그래도 큰 고비를 하나 넘겼으니 CLASS 5에 더 가까워지게 되었다. 제발 남은 문제들은 이것보단 쉬웠으면 좋겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/9328

← Previous Post Next Post →